package week02

// 46. 全排列
// https://leetcode-cn.com/problems/permutations/

func permute(nums []int) [][]int {
	return permute2(nums, []int{}, make([]bool, len(nums)), [][]int{}, 0)
}

// 依次遍历所有出现的数字
// 从未使用的数字中选出一个放入当前位置
func permute2(nums, temp []int, used []bool, ans [][]int, index int) [][]int {
	if len(nums) == index {
		var res = make([]int, len(temp))
		copy(res, temp)
		return append(ans, res)
	}

	for i, num := range nums {
		if used[i] {
			continue
		}
		used[i] = true
		temp = append(temp, num)
		// 处理下一个位置
		ans = permute2(nums, temp, used, ans, index+1)
		// 还原现场
		used[i] = false
		temp = temp[:len(temp)-1]
	}
	return ans
}
